Search for: All records

Abstract We study versions of the tree pigeonhole principle,$$\mathsf {TT}^1$$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether$$\mathsf {TT}^1$$is$$\Pi ^1_1$$-conservative over the ordinary pigeonhole principle,$$\mathsf {RT}^1$$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike$$\mathsf {RT}^1$$, the problem$$\mathsf {TT}^1$$is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of$$\mathsf {TT}^1$$. 

We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem P is the strongest problem with codomaixn ω that is Weihrauch reducible to P. We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature. 

Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths. 

We prove the following result: there is a family R = ⟨ R 0 , R 1 , … ⟩ of subsets of ω such that for every stable coloring c : [ ω ] 2 → k hyperarithmetical in R and every finite collection of Turing functionals, there is an infinite homogeneous set H for c such that none of the finitely many functionals map R ⊕ H to an infinite cohesive set for R. This provides a partial answer to a question in computable combinatorics, whether COH is omnisciently computably reducible to SRT 2 2 .